The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN:
0471353817
Pub Date:
03/01/99
Preface
Chapter 1Introduction
Chapter 2Twofish Design Goals
Chapter 3Twofish Building Blocks
3.1 Feistel Networks
3.2 Whitening
3.3 S-boxes
3.4 MDS Matrices
3.5 Pseudo-Hadamard Transforms
3.6 Key Schedule
Chapter 4Twofish
4.1 The Function
F
4.2 The Function
g
4.3 The Key Schedule
4.3.1 Additional Key Lengths
4.3.2 The Function
h
4.3.3 The Key-dependent S-boxes
4.3.4 The Expanded Key Words
Kj
4.3.5 The Permutations
q
0 and
q
1
4.4 Round Function Overview
Chapter 5Performance of Twofish
5.1 Performance on Large Microprocessors
5.1.1 Keying Options
5.1.2 Code and Data Size
5.1.3 Large Memory Implementations
5.1.4 Total Encryption Times
5.1.5 Hash Function Performance
5.1.6 Language, Compiler, and Processor Choice
5.2 Performance on Smart Cards
5.2.1 RAM Usage
5.2.2 Encryption Speed and Key Agility
5.2.3 Code Size
5.3 Performance on the Alpha
5.4 Performance on Future Microprocessors
5.5 Hardware Performance
Chapter 6Twofish Design Philosophy
6.1 Performance-Driven Design
6.1.1 Performance-driven Tradeoffs
6.2 Conservative Design
6.3 Simple Design
6.3.1 Reusing Primitives
6.3.2 Reversibility
6.4 S-boxes
6.4.1 Large S-boxes
6.4.2 Algorithmic S-boxes
6.4.3 Key-dependent S-boxes
6.5 The Key Schedule
6.5.1 Performance Issues
Chapter 7The Design of Twofish
7.1 The Round Structure
7.1.1 Common Block Cipher Structures
7.2 The Key-dependent S-boxes
7.2.1 The Fixed Permutations
q
0 and
q
1
7.2.2 The S-boxes.
7.2.3 Exhaustive and Statistical Analysis
7.3 MDS Matrix
7.3.1 Non-key-dependent Coefficients
7.3.2 Implementation Issues
7.3.3 Preserving Diffusion Properties after Rotation
7.3.4 Rotational Uniqueness of Output Vectors
7.3.5 Maximizing the Minimal Hamming Distance
7.4 PHT
7.4.1 Eliminating the PHT
7.4.2 Diffusion and the Least Significant Bit
7.5 Key Addition
7.6 Feistel Combining Operation
7.7 Use of Different Groups
7.8 Diffusion in the Round Function
7.8.1 Changes Induced by
F
7.9 One-bit Rotation
7.9.1 Reason for Rotations
7.9.2 Downsides to Rotations
7.9.3 Converting to a Pure Feistel Structure
7.10 The Number of Rounds
Chapter 8Design of the Twofish Key Schedule
8.1 Round Subkeys
8.1.1 Equivalence of Round Subkeys
8.1.2 Equivalent keys
8.2 Controlling Changes in Round Subkeys
8.2.1 XOR Difference Sequences in A and B
8.2.2 Byte Sequences with Given Difference
8.2.3 Identical Byte Sequences
8.2.4 The A and B Sequences
8.2.5 The Sequence (
K
2
i
,
K
2
i
+1)
8.2.6 Difference Sequences in the Subkeys
8.3 The Round Function
8.4 Properties of the Key Schedule and Cipher
8.4.1 Equivalent Keys
8.4.2 Self-Inverse Keys
8.4.3 Pairs of Inverse Keys
8.4.4 Simple Relations
8.5 Key-dependent Characteristics and Weak Keys
8.6 Reed-Solomon Code
Chapter 9Cryptanalysis of Twofish
9.1 A Meet-in-the-Middle Attack on Twofish
9.1.1 Results of the Attack
9.1.2 Overview of the Attack
9.1.3 Attacking Twofish with Fixed
S
and no Whitening
9.1.4 Attacking Twofish with Fixed
S
9.1.5 Attacking Normal Twofish
9.2 Differential Cryptanalysis
9.2.1 Results of the Attack
9.2.2 Overview of the Attack
9.2.3 Building the Batches
9.2.4 Mounting the Attack
9.2.5 Lessons from the Analysis
9.3 Extensions to Differential Cryptanalysis
9.3.1 Higher-Order Differential Cryptanalysis
9.3.2 Truncated Differentials
9.4 Search for the Best Differential Characteristic
9.4.1 Differentials of the S-boxes
9.4.2 Differentials of
F
9.4.3 Differentials of the Round Function
9.4.4 Multi-round Patterns
9.4.5 Results
9.4.6 Other Problems for the Attacker
9.4.7 Best S-box Differential
9.4.8 Other Variants
9.4.9 Further Work
9.4.10 Conclusion
9.5 Linear Cryptanalysis
9.5.1 Multiple Linear Approximations
9.5.2 Non-linear Cryptanalysis
9.5.3 Generalized Linear Cryptanalysis
9.5.4 Partitioning Cryptanalysis
9.5.5 Differential-linear Cryptanalysis
9.6 Interpolation Attack
9.7 Partial Key Guessing Attacks
9.8 Related-key Cryptanalysis
9.8.1 Resistance to Related-key Slide Attacks
9.8.2 Resistance to Related-key Differential Attacks
9.8.3 The Zero Difference Case
9.8.4 Other Difference Sequences
9.8.5 Probability of a Successful Attack with One Related-key Query
9.8.6 Conclusions
9.9 A Chosen-key Attack
9.9.1 Overview of the Attack
9.9.2 Finding a Key Pair
9.9.3 Choosing the Plaintexts to Request
9.9.4 Extracting the Key Material
9.10 Side-Channel Cryptanalysis and Fault Analysis
9.11 Attacking Simplified Twofish
9.11.1 Twofish with Known S-boxes
9.11.2 Twofish without Round Subkeys
9.11.3 Twofish with Non-bijective S-boxes
9.12 Trap Doors in Twofish
Chapter 10Using Twofish
10.1 Chaining Modes
10.2 One-Way Hash Rinctions
10.3 Message Authentication Codes
10.4 Pseudorandom Number Generators
10.5 Larger Keys
10.6 Additional Block Sizes
10.7 More or Fewer Rounds
10.8 Family Key Variant: Twofish-FK
10.8.1 Analysis
Chapter 11Historical Remarks
Chapter 12Conclusions and Further Work
References
Appendix A
Appendix B
Appendix C
Index